# leetcode 18 四数之和

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        n = len(nums)
        ret = set()
        sorted_nums = sorted(nums)  # 从小到大排序
        for i in range(n):
            if sorted_nums[i] > target and target > 0:
                break
            for j in range(i + 1, n):
                left = j + 1
                right = n - 1
                while left < right: # 双指针， 初始左指针指向 j + 1, 右指针指向 n - 1
                    tmp = sorted_nums[i] + sorted_nums[j] + sorted_nums[left] + sorted_nums[right]
                    if tmp == target:
                        ret.add(tuple([sorted_nums[i], sorted_nums[j], sorted_nums[left], sorted_nums[right]]))
                        left += 1
                    elif tmp < target: # 比target小，右移左指针
                        left += 1
                    else:
                        right -= 1  # 比target大，左移右指针
        return [list(i) for i in ret]
